package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1218 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int longestSubsequence(int[] arr, int difference) {
            Map<Long, Integer> memo = new HashMap<>();
            int res = 1;
            for (long num : arr) {
                if (memo.containsKey(num - difference)) {
                    res = Math.max(res, memo.get(num - difference) + 1);
                    memo.put(num, memo.get(num - difference) + 1);
                } else {
                    memo.put(num, 1);
                }
            }

            return res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.longestSubsequence(InputUtil.toIntegerArray(" [1,2,3,4]"), 1));
        System.out.println(solution.longestSubsequence(InputUtil.toIntegerArray(" [1,3,5,7]"), 1));
        System.out.println(solution.longestSubsequence(InputUtil.toIntegerArray("[1,5,7,8,5,3,4,2,1]"), -2));
        System.out.println(solution.longestSubsequence(InputUtil.toIntegerArray("[4,12,10,0,-2,7,-8,9,-9,-12,-12,8,8]"), 0));
    }

    public static void main(String[] args) throws Exception {
        LC1218 an = new LC1218();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
